package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/daily-temperatures/">每日温度(Daily Temperatures)</a>
 * <p>给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。</p>
 * <pre>
 * 示例 1:
 *      输入: temperatures = [73,74,75,71,69,72,76,73]
 *      输出: [1,1,4,2,1,1,0,0]
 *
 * 示例 2:
 *      输入: temperatures = [30,40,50,60]
 *      输出: [1,1,1,0]
 *
 * 示例 3:
 *      输入: temperatures = [30,60,90]
 *      输出: [1,1,0]
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= temperatures.length <= 10^5</li>
 *     <li>30 <= temperatures[i] <= 100</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/11/4 14:54
 */
public class LC0739DailyTemperatures_M {

    static class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            // 从左到右遍历温度数组。使用单调递减的栈来保存每日温度
            // 如果后续温度，小于当前温度，将对应下标加到栈中。
            // 如果后续温度，大于当前温度，进行清算
            Deque<Integer> stack = new ArrayDeque<>();
            int[] ans = new int[temperatures.length];
            for (int i = 0; i < temperatures.length; i++) {
                // 当日温度。如果当日温度大于之前某一天的温度，则当日温度为之前某一天温度的更高温度
                // 例如：73,74,75,71,69,72,76,73
                // 下标： 0  1  2  3  4  5  6  7
                //      num           stack
                //     0 ：73           73
                //     1 ：74           74   -->73出74入: ans[0]= 1-0=1
                //     2 ：75           75   -->74出75入: ans[1]= 2-1=1
                //     3 ：71           75 71
                //     4 ：69           75 71 69
                //     5 ：72           75 71 --> 69出：    ans[4] = 5-4=1
                //                      75 72 --> 71出72入：ans[3] = 5-3=2
                //     6 ：76           75    --> 72出：ans[5]= 6-5=1
                //                      76    --> 75出76入：ans[2]= 6-2=4
                //     7 ：73           76 73
                while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peekLast()] ) {
                    Integer idx = stack.pollLast();
                    ans[idx] = i - idx;
                }
                stack.offerLast(i);
            }
            return ans;
        }


        public int[] dailyTemperatures2(int[] temperatures) {
            // 从右到左遍历温度数组。使用单调递减的栈来保存每日温度
            // 如果当前温度，小于栈顶元素，值记为1，并将对应下标加到栈中。
            // 如果当前温度，大于栈顶温度，将栈中小于当前温度的下标弹出栈，当当前文档对应下标加入栈中
            Deque<Integer> stack = new ArrayDeque<>();
            int[] ans = new int[temperatures.length];
            for (int i = temperatures.length - 1; i >= 0; i--) {
                while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peekLast()]) {
                    stack.pollLast();
                }
                if (!stack.isEmpty()) {
                    ans[i] = stack.peekLast() - i;
                }
                stack.offerLast(i);
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.dailyTemperatures(new int[]{73, 73, 75, 71, 69, 72, 76, 73}));
        Printer.printArrayInt(solution.dailyTemperatures2(new int[]{73, 73, 75, 71, 69, 72, 76, 73}));
    }
}
